package day1_array.leetcode;

/**
 * 长度最小的子数组 - 滑动窗口
 * @Author: yuisama
 * @Date: 2022/3/30 11:54
 * @Description:
 */
public class Num209_MinSubArray {
    // 滑动窗口
    // 时间复杂度O(n),空间复杂度O(1)
    public int minSubArrayLen(int target, int[] nums) {
        // 初始化ret为数组长度 + 1，不可能有这个解
        int ret = nums.length + 1;
        // nums[l..r]为滑动窗口
        int l = 0;
        int r = -1;
        int sum = 0;
        while (l < nums.length) {
            if (r < nums.length - 1 && sum < target) {
                // 滑动右区间
                sum += nums[++ r];
            }else {
                // sum >= target或r走到头
                // 滑动左区间
                sum -= nums[l ++];
            }

            if (sum >= target) {
                ret = Math.min(ret,r - l + 1);
            }
        }
        if (ret == nums.length + 1) {
            ret = 0;
        }
        return ret;
    }
}
